/**
 * 15. 三数之和
 * https://leetcode-cn.com/problems/3sum/
 */

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
  const { length } = nums;
  if (length < 3) return [];
  // 先进行从小到大排序
  nums.sort((a, b) => a - b);
  // 利用三指针进行匹配查找，其中右侧两个指针同时向内收拢让时间复杂度降低
  const result = [];
  const lastI = length - 3;
  const lastIndex = length - 1;
  let i = 0;
  while (i <= lastI) {
    const iv = nums[i];
    const is = -iv;
    let l = i + 1;
    let r = lastIndex;
    while (l < r) {
      const lv = nums[l];
      const rv = nums[r];
      const s = lv + rv;
      let moveL = true;
      if (s === is) {
        result.push([iv, lv, rv]);
      } else if (s > is) {
        moveL = false;
      }
      if (moveL) {
        do {
          l += 1;
        } while (nums[l] === lv && l < r);
      } else {
        do {
          r -= 1;
        } while (nums[r] === rv && l < r);
      }
    }
    do {
      i += 1;
    } while (nums[i] === iv && i <= lastI);
  }
  return result;
}

console.log(threeSum([-1, 0, 1, 2, -1, -4]));
console.log(threeSum([-2, 0, 1, 1, 2]));
console.log(threeSum([-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4]));
